package FebruaryOn2022;

import java.util.ArrayList;
import java.util.List;

/**
 * Copyright (c) XuQunXing Technologies Co., Ltd. 2021-2021. All rights reserved.
 * Description:
 * User: x30003433
 * Date: 2022-02-08
 * Time: 14:12
 */
public class FindTheMinimumNumberOfFibonacci {
    public static void main(String[] args) {
        System.out.println(findMinFibonacciNumbers(7));//2
        System.out.println(findMinFibonacciNumbers(10));//2
        System.out.println(findMinFibonacciNumbers(19));//3
    }

    public static int findMinFibonacciNumbers(int k) {
        // 1.找到不大于k的裴波那契数列
        List<Integer> list = new ArrayList<>();
        list.add(1);
        int a = 1, b = 1;
        while (a + b <= k) {
            int tmp = a + b;
            list.add(tmp);
            a = b;
            b = tmp;
        }
        // 2.依次往后减
        int ans = 0;
        for (int i = list.size() - 1; i >= 0 && k > 0; i--) {
            if (list.get(i) <= k) {
                k = k - list.get(i);
                ans++;

            }
        }
        return ans;
    }
}